﻿\subsection{Алгоритм построения антисловаря}
\label{subsection:bigexp-algo}

Пусть $L$~--- $\beta$-свободный язык первого уровня над $\Sigma = \{0,\ldots,k{-}1\}$, $r\in L$.
Построим слово $u$ следующим образом: оно будет начинаться со слова $r$, иметь длину
$\lceil|r| \cdot \beta\rceil$ и период $|r|$. Тогда $u$ будет запрещённым в $L$,
а если $u$ не содержит собственных подслов вида $ztz$, таких что $|ztz|/|zt| \ge \beta$,
то $u$ будет лежать в антисловаре $L$. Далее мы будем называть слово $r$ \textit{корнем}
запрещённого слова и использовать обозначения $r = xy$, $u = xyx$.

Рассмотрим конечное приближение антисловаря, в котором длина корней запрещённых
слов ограничена сверху числом $R$. Для построения приближения нужно перебрать все слова
$r\in L$, такие что $|r| \le R$, достроить их до слова $u$ и, при необходимости, добавить последнее
в антисловарь.

В алгоритме, предложенном в \cite{Shur-Algo}, предлагается перебирать корни в порядке
возрастания их длин. При этом все корни хранятся во вспомогательной очереди~$Q$, а все
уже найденные слова из антисловаря~--- в боре $T$:
\texttt{\begin{tabbing}
01. $Q \leftarrow "0"$\\
02. пока \= $Q \neq \emptyset$ \\
03. \> $r \leftarrow Q$\\
04. \> построить $u$ (см. построение выше)\\
05. \> если \= ни одно собственное подслово $u$ не лежит в $T$\\
06. \>\> $T \leftarrow u$\\
07. \> если \= $|r| < R$ \\
08. \>\> для \= всех $c$ от '0' до $\min(maxLetter(r){+}1, k{-}1)$\\
09. \>\>\> $rn \leftarrow r + c$\\
10. \>\>\> если \= у $rn$ нет суффикса из $T$\\
11. \>\>\>\> $Q \leftarrow rn$\\
12. конец цикла
\end{tabbing}}
Алгоритм основан на том, что, за счёт перебора корней в порядке возрастания их длин,
в момент проверки $u$ все минимальные запрещённые слова меньшей длины уже лежат в $T$.
Потенциальные корни запрещённых слов всегда являются разрешёнными (из-за проверки в строке 10),
поэтому для проверки в строке 5 достаточно рассмотреть суффиксы подслов из $u[1..(|r|+1)]$,
$u[1..(|r|+2)]$, \ldots, $u$. Проверку на принадлежность бору какого-либо суффикса слова
можно провести за линейное время (вместо суффиксов исходного слова можно проверять префиксы
перевёрнутого), то есть за $O(|r|\cdot\beta)$. Поскольку $|x| \le |r|/(k-2)$, сложность
проверки условия в строке 5 составляет $O(|r|^2\beta / k)$, или $O(|r|^2/k)$, если считать
$\beta$ константой.

Приведённый выше алгоритм позволяет для широкого класса языков быстро строить большие
антисловари (суммарная длина слов в которых достигает десятков миллионов букв). Однако,
в случае языков первого уровня, расходы на размещение очереди $Q$ в памяти становятся
слишком значительными~--- поскольку избегаемая экспонента мала, корни, которые
достраиваются до минимальных запрещённых слов, встречаются редко. Например, при $|\Sigma|=10$ и
$|r|\le 85$ суммарная длина корней, одновременно хранящихся в очереди $Q$, превышает 2 млрд.
символов, однако количество корней, которые достраиваются до слов из антисловаря, составляет
всего лишь $1184$.

В данной работе мы рассматриваем алгоритм построения антисловаря, в котором потенциальные
корни перебираются рекурсивно. Это позволит нам избавиться от хранения очереди $Q$, но
потребует разработать эффективный метод проверки того, является ли достроенное из корня запрещённое
слово $u$ минимальным запрещённым (поскольку, в случае рекурсивного перебора, мы не можем
гарантировать, что все слова длины, меньшей $|u|$, уже добавлены в антисловарь).
Приведём общую схему работы нашего алгоритма:
\texttt{\begin{tabbing}
\noindent\textsc{build}($r$) (рекурсивный перебор корней). \label{pr-bigexp} \\
01. построить по корню $r$ слово $u$ (см. построение выше)\\
02. если \= $u$ является минимальным запрещённым словом\\
03. \> добавить $P(u)$ в антисловарь\\
04. если \= $|r| < R$\\
05. \> для \= $c \in \{0,1\}$\\
06. \>\> $rn \leftarrow P^{-1}(P(r) + c)$\\
07. \>\> если \= в $rn$ нет запрещённого суффикса\\
08. \>\>\> \textsc{build}($rn$)\\
09. конец процедуры
\end{tabbing}}
Если $|\Sigma| = \{0,1,\ldots,k{-}1\}$, для перебора всех корней достаточно вызвать процедуру
\textsc{build} от слова $w = 01\ldots(k{-}3)(k{-}2)$. Мы пользуемся тем, что ко всем словам
языков нижнего уровня (в частности, к корням минимальных запрещённых слов) можно применить
кодировку Пансьё~--- мы перебираем только два варианта очередной буквы корня в строках 5-8
и строим антисловарь из кодов Пансьё, а не из самих запрещённых слов (см.
параграф~\ref{subsection:bigexp-intro}).

В параграфах~\ref{subsection:bigexp-sufarr} и \ref{subsection:bigexp-forbidden} описан метод
эффективной реализации проверок в строках 2 и 7. В параграфе~\ref{subsection:bigexp-results}
приведены численные результаты, которые были получены с помощью этого алгоритма.

